#
# @lc app=leetcode.cn id=1305 lang=python3
#
# [1305] 两棵二叉搜索树中的所有元素
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        result1 = self.inorder(root1)
        result2 = self.inorder(root2)
        i = 0
        j = 0
        result = []
        while (i < len(result1) or j < len(result2)):
            if (j >= len(result2) or (i < len(result1) and result1[i] <= result2[j])):
                result.append(result1[i])
                i += 1
            else:
                result.append(result2[j])
                j += 1

        return result

# @lc code=end
